package leetcode.daily;

import java.util.HashMap;
import java.util.Map;

/**
 * @author : zx
 * @version V1.0
 */
public class easy_med_20201216 {

    /**
     * 942. 增减字符串匹配
     * 给定只含 "I"（增大）或 "D"（减小）的字符串 S ，令 N = S.length。
     *
     * 返回 [0, 1, ..., N] 的任意排列 A 使得对于所有 i = 0, ..., N-1，都有：
     *
     * 如果 S[i] == "I"，那么 A[i] < A[i+1]
     * 如果 S[i] == "D"，那么 A[i] > A[i+1]
     *
     *
     * 示例 1：
     *
     * 输入："IDID"
     * 输出：[0,4,1,3,2]
     * 示例 2：
     *
     * 输入："III"
     * 输出：[0,1,2,3]
     * 示例 3：
     *
     * 输入："DDI"
     * 输出：[3,2,0,1]
     *
     *
     * 提示：
     *
     * 1 <= S.length <= 10000
     * S 只包含字符 "I" 或 "D"。
     */
    public int[] diStringMatch(String S) {
        /**
         * 按顺序进行 无论是 I 还是 D 选中的数字一定是 剩余 最大 或者 最小的数字
         */
        int[] res = new int[S.length()+1];
        char[] c = S.toCharArray();
        int max = S.length();
        int min = 0;
        for(int i = 0; i < c.length; i++){
            if(c[i] == 'I'){
                res[i] = min++;
            }else{
                res[i] = max--;
            }
        }
        res[S.length()] = max;
        return res;
    }

    /**
     * 432. 全 O(1) 的数据结构
     * 请你实现一个数据结构支持以下操作：
     *
     * Inc(key) - 插入一个新的值为 1 的 key。或者使一个存在的 key 增加一，保证 key 不为空字符串。
     * Dec(key) - 如果这个 key 的值是 1，那么把他从数据结构中移除掉。否则使一个存在的 key 值减一。如果这个 key 不存在，这个函数不做任何事情。key 保证不为空字符串。
     * GetMaxKey() - 返回 key 中值最大的任意一个。如果没有元素存在，返回一个空字符串"" 。
     * GetMinKey() - 返回 key 中值最小的任意一个。如果没有元素存在，返回一个空字符串""。
     *
     *
     * 挑战：
     *
     * 你能够以 O(1) 的时间复杂度实现所有操作吗？
     */
    class AllOne {

        private Node head;
        private Node tail;
        private Map<String, Node> map;

        /** Initialize your data structure here. */
        public AllOne() {
            head = new Node("head", -1);
            tail = new Node("tail", -1);
            head.next = tail;
            tail.prev = head;
            map = new HashMap<>();
        }

        /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
        public void inc(String key) {
            // merge函数会判断map中是否存在key，如果不存在就会用merge函数的第二个参数作为key的value存入map
            // 如果key已经存在，就会利用merge函数的第三个参数，这个参数接收一个函数式接口
            // 该函数式接口会对已经存在的key的value和你提供的value进行操作（就是merge函数的第二个参数）
            // 由于本题只需要对已经存在的key的value加一，故不需要操作你提供的value
            // merge函数会将已经存在的key和函数式接口返回的value关联起来
            // 由于本题要求，故在函数式接口中直接返回原来的value即可
            map.merge(key, new Node(key, 1), (node1, node2) -> {
                node1.value++;
                return node1;
            });
            map.get(key).moveToTail(head, tail);
        }

        /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
        public void dec(String key) {
            Node temp = map.get(key);
            // computeIfPresent函数其实本质上与merge函数基本相同
            // computeIfPresent函数与merge函数的区别在于computeIfPresent函数不会提供默认值
            // 也就意味着如果你提供的key不在map中computeIfPresent函数什么也不做
            // 相反如果key存在就会执行你提供的函数式接口里面的操作（computeIfPresent函数的第二个参数）
            // 如果你在函数式接口里面返回了null，那computeIfPresent函数会将该key删除（当前前提是该key存在）
            map.computeIfPresent(key, (k, node) -> {
                node.value--;
                if (node.value == 0) {
                    return null;
                }
                return node;
            });
            if (map.containsKey(key)) {
                map.get(key).moveToHead(head);
            } else {
                if (temp != null) {
                    temp.delete();
                }
            }
        }

        /** Returns one of the keys with maximal value. */
        public String getMaxKey() {
            if (map.isEmpty()) {
                return "";
            } else {
                return tail.prev.key;
            }
        }

        /** Returns one of the keys with Minimal value. */
        public String getMinKey() {
            if (map.isEmpty()) {
                return "";
            } else {
                return head.next.key;
            }
        }
    }

    class Node {

        String key;
        int value;
        Node prev;
        Node next;

        public Node(String key, int value) {
            this.key = key;
            this.value = value;
            prev = null;
            next = null;
        }

        public void moveToTail(Node head, Node tail) {
            if (prev == next && prev == null) {
                next = head.next;
                prev = head;
                next.prev = this;
                head.next = this;
            } else if (next != tail) {
                while (value > next.value && next != tail) {
                    prev.next = next;
                    next.prev = prev;
                    Node temp = next;
                    next = temp.next;
                    temp.next = this;
                    prev = temp;
                    next.prev = this;
                }
            }
        }

        public void moveToHead(Node head) {
            if (prev != head) {
                if (value < prev.value) {
                    prev.next = next;
                    next.prev = prev;
                    Node temp = prev;
                    next = temp;
                    prev = temp.prev;
                    prev.next = this;
                    temp.prev = this;
                }
            }
        }

        public void delete() {
            prev.next = next;
            next.prev = prev;
            prev = null;
            next = null;
        }
    }


    /**
     * 1160. 拼写单词
     * 给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。
     *
     * 假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。
     *
     * 注意：每次拼写（指拼写词汇表中的一个单词）时，chars 中的每个字母都只能用一次。
     *
     * 返回词汇表 words 中你掌握的所有单词的 长度之和。
     *
     *
     *
     * 示例 1：
     *
     * 输入：words = ["cat","bt","hat","tree"], chars = "atach"
     * 输出：6
     * 解释：
     * 可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。
     * 示例 2：
     *
     * 输入：words = ["hello","world","leetcode"], chars = "welldonehoneyr"
     * 输出：10
     * 解释：
     * 可以形成字符串 "hello" 和 "world"，所以答案是 5 + 5 = 10。
     *
     *
     * 提示：
     *
     * 1 <= words.length <= 1000
     * 1 <= words[i].length, chars.length <= 100
     * 所有字符串中都仅包含小写英文字母
     */
    public int countCharacters(String[] words, String chars) {
        return 0;
    }

}
